package psn.zjk.career.interview.algorithm.sort;

import java.util.Arrays;

public class QuickSort {

    public int[] sort(int[] sourceArray) {
        int[] ints = Arrays.copyOf(sourceArray, sourceArray.length);
        quickSort(ints, 0, ints.length - 1);
        return ints;
    }

    private void quickSort(int[] ints, int left, int right) {
        if (left < right) {
            int partionIndex = partionIndex(ints, left, right);
            quickSort(ints, left, partionIndex - 1);
            quickSort(ints, partionIndex + 1, right);
        }
    }

    private int partionIndex(int[] ints, int left, int right) {
        int base = left;//基数：用于比较
        int index = left + 1;//记录比基数小的数的下标
        for (int i = index; i <= right; i++) {
            if (ints[i] > ints[base]) {
                swap(ints, i, index);
                index++;
            }
        }
        swap(ints, base, index - 1);//这里减一是因为，index记录的是比基数小的，而index左边一定是比基数大的
        return index - 1;
    }

    private void swap(int[] ints, int i, int index) {
        if (i != index) {
            int tmp = ints[i];
            ints[i] = ints[index];
            ints[index] = tmp;
        }

    }


    public static void main(String[] args) throws Exception {
        int[] numbers = {12, 15, 1, 18, 2, 35, 30, 11, 312};
        Arrays.stream(numbers).forEach(num -> {
            System.out.print(num + " ");
        });
        System.out.println();
        //数组不建议用lambada
        Arrays.stream(new QuickSort().sort(numbers)).forEach(num -> {
            System.out.print(num + " ");
        });
    }
}